The disclosed embodiments relate generally to computer-implemented methods and apparatus for performing hierarchical sampling and computing of numerical values such as percentiles.
A percentile is a measure used in statistics indicating the value below which a given percentage of data points in a group of data points fall. For example, the 20th percentile is the value below which 20 percent of the data points may be found.
Typically, to identify an nth percentile of a set of data values, the set of data values are sorted and the nth percentile is then identified. Unfortunately, sorting is an extremely time-consuming process. Therefore, as the set of data values increases in size, the time it takes to identify the nth percentile also increases.